package dataStructure.tree;

/**
 * @author lhn
 * @date 2024-09-03 19:54
 */

public class ThreadBinaryTreeDemo {
    public static void main(String[] args) {
        ThreadBinaryTree_ threadBinaryTree = new ThreadBinaryTree_();
        HeroNodePlus heroNodePlus1 = new HeroNodePlus(1, "用户1");
        HeroNodePlus heroNodePlus2 = new HeroNodePlus(3, "用户2");
        HeroNodePlus heroNodePlus3 = new HeroNodePlus(6, "用户3");
        HeroNodePlus heroNodePlus4 = new HeroNodePlus(8, "用户4");
        HeroNodePlus heroNodePlus5 = new HeroNodePlus(10, "用户5");
        HeroNodePlus heroNodePlus6 = new HeroNodePlus(14, "用户6");

        /**
                     1
                   /   \
                  3     6
                 / \   / \
                8  10 14
        */
        threadBinaryTree.setRoot(heroNodePlus1);
        heroNodePlus1.setLeft(heroNodePlus2);
        heroNodePlus1.setRight(heroNodePlus3);
        heroNodePlus2.setLeft(heroNodePlus4);
        heroNodePlus2.setRight(heroNodePlus5);
        heroNodePlus3.setLeft(heroNodePlus6);

        //6号节点进行测试
        threadBinaryTree.inThreadedNode();

        HeroNodePlus left = heroNodePlus3.getLeft();
        HeroNodePlus right = heroNodePlus3.getRight();
        if (heroNodePlus5.isLeftThread()) {
            System.out.print("heroNodePlus3 的前驱节点为：");
        } else {
            System.out.print("heroNodePlus3 没有前驱节点");
        }
        System.out.println(left);

        if (heroNodePlus3.isRightThread()) {
            System.out.print("heroNodePlus3 的后驱节点为：");
        } else {
            System.out.print("heroNodePlus3 没有后驱节点");
        }
        System.out.println(right);

        threadBinaryTree.inOrderThreadedList(); //中序遍历线索化二叉树
        /**
        -找有前驱的->8-后驱->3-右节点->10-后驱->1-找有前驱的->14-后驱->6
        */
    }
}

class ThreadBinaryTree_ {
    private HeroNodePlus root;
    private HeroNodePlus pre = null;    //在线序化时，使用该记录的前驱节点
    public void setRoot(HeroNodePlus root) {
        this.root = root;
    }
    public HeroNodePlus getRoot() {
        return root;
    }

    //重载
    public void inThreadedNode() {
        this.inThreadedNode(root);
    }
    //中序线索化
    /**
    * 中序线索化
     * @param node  当前需要线索化的节点
    */
    public void inThreadedNode (HeroNodePlus node) {
        if (node == null) {
            return;
        }

        //1.线索化左子节点
        inThreadedNode(node.getLeft());

        //2.线索化当前节点
        //处理当前节点的前驱节点
        if (node.getLeft() == null) {
            node.setLeft(pre);  //当前节点的前驱节点指向pre
            node.setLeftThread(true);   //当前节点是线索化节点

        }

        //处理当前节点的后驱节点
        if (pre != null && pre.getRight() == null) {  //当前节点没有右子节点
            pre.setRight(node);  //当前节点的后继节点指向
            pre.setRightThread(true);   //当前节点是线索化节点
        }

        //处理完当前节点，当前节点成为下一个节点的前驱节点
        pre = node;

        //3.线索化右子节点
        inThreadedNode(node.getRight());

    }

    //线索化后，某些节点的左右指针发生改变，不能用原来的遍历方法
    //中序遍历线索化二叉树
    public void inOrderThreadedList() {
        HeroNodePlus node = this.root;
        while (node != null) {
            //找到leftThread = true的节点
            while (node.isLeftThread() == false) {
                node = node.getLeft();
            }
            System.out.println(node);
            while (node.isRightThread() == true) {
                node = node.getRight();
                System.out.println(node);
            }

            //当前节点的没有后驱节点，继续遍历右子树
            node = node.getRight();
        }
    }

    //前序遍历
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    //中序遍历
    public void inOrder() {
        if (this.root != null) {
            this.root.inOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    //后序遍历
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    public HeroNodePlus preOrderFindNode(int no) {
        if (this.root != null) {
            return this.root.preOrderFindNode(no);
        } else {
            System.out.print("二叉树为空，无法查找 ");
            return null;
        }
    }

    public HeroNodePlus inOrderFindNode(int no) {
        if (this.root != null) {
            return this.root.inOrderFindNode(no);
        } else {
            System.out.print("二叉树为空，无法查找 ");
            return null;
        }
    }

    public HeroNodePlus postOrderFindNode(int no) {
        if (this.root != null) {
            return this.root.postOrderFindNode(no);
        } else {
            System.out.print("二叉树为空，无法查找 ");
            return null;
        }
    }

    public boolean delNode(int no) {
        if (this.root != null) {
            if (this.root.getNo() == no) {
                this.root = null;
                return true;
            } else {
                return this.root.delNode(no);
            }
        } else {
            System.out.print("二叉树为空，无法删除 ");
            return false;
        }
    }
}

//HeroNode加强版拥有前驱和后驱
class HeroNodePlus {
    private int no; //编号
    private String name;    //名字
    private HeroNodePlus left; //左子节点
    private HeroNodePlus right; //右子节点
    private boolean isLeftThread;   //true 表示左边节点是前驱节点，false表示左边节点是左节点
    private boolean isRightThread;  //true 表示右边节点是后驱节点，false表示右边节点是右节点

    public HeroNodePlus() {
    }

    public HeroNodePlus(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNodePlus getLeft() {
        return left;
    }

    public void setLeft(HeroNodePlus left) {
        this.left = left;
    }

    public HeroNodePlus getRight() {
        return right;
    }

    public void setRight(HeroNodePlus right) {
        this.right = right;
    }

    public boolean isLeftThread() {
        return isLeftThread;
    }

    public void setLeftThread(boolean leftThread) {
        isLeftThread = leftThread;
    }

    public boolean isRightThread() {
        return isRightThread;
    }

    public void setRightThread(boolean rightThread) {
        isRightThread = rightThread;
    }

    @Override
    public String toString() {
        return "HeroNodePlus{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    //前序遍历
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    //中序遍历
    public void inOrder() {
        if (this.left != null) {
            this.left.inOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.inOrder();
        }
    }

    //后序遍历
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }

    //前序查找
    public HeroNodePlus preOrderFindNode(int no) {
        System.out.println("进入前序查找");
        if (this.no == no) {
            return this;
        }
        HeroNodePlus resNodePlus = null;
        //左递归查找
        if (this.left != null) {
            resNodePlus = this.getLeft().preOrderFindNode(no);
        }
        if (resNodePlus != null) {
            return resNodePlus;
        }
        //右递归查找
        if (this.right != null) {
            resNodePlus = this.getRight().preOrderFindNode(no);
        }
        if (resNodePlus != null) {
            return resNodePlus;
        }
        return resNodePlus;
    }

    //中序查找
    public HeroNodePlus inOrderFindNode(int no) {

        HeroNodePlus resNodePlus = null;
        //左递归查找
        if (this.left != null) {
            resNodePlus = this.getLeft().inOrderFindNode(no);
        }
        if (resNodePlus != null) {
            return resNodePlus;
        }
        System.out.println("进入中序查找");
        if (this.no == no) {
            return this;
        }
        //右递归查找
        if (this.right != null) {
            resNodePlus = this.getRight().inOrderFindNode(no);
        }
        if (resNodePlus != null) {
            return resNodePlus;
        }
        return resNodePlus;
    }

    public HeroNodePlus postOrderFindNode(int no) {

        HeroNodePlus resNodePlus = null;
        //左递归查找
        if (this.left != null) {
            resNodePlus = this.getLeft().postOrderFindNode(no);
        }
        if (resNodePlus != null) {
            return resNodePlus;
        }
        //右递归查找
        if (this.right != null) {
            resNodePlus = this.getRight().postOrderFindNode(no);
        }
        if (resNodePlus != null) {
            return resNodePlus;
        }
        System.out.println("进入后序查找" + this.getNo() );
        if (this.no == no) {
            return this;
        }
        return resNodePlus;
    }

    //递归删除节点
    //1.需求：如果要删除的节点是叶子节点，则删除该节点
    //2.如果要删除的节点是非叶子节点，则删除该子树
    public boolean delNode(int no) {
        System.out.println("进入删除节点" + this.getNo());
        //如果当前节点的左子节点不为空，并且左子节点的编号等于要删除的节点的编号，则删除
        if (this.left != null && this.left.no == no) {
            this.left = null;
            return true;
        }
        //右同理
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return true;
        }
        //如果左右子树都不为空，则继续递归
//        if (this.left != null) {
//            //如果左递归删除成功，则返回true;删除失败，则继续右递归
//            if (this.left.delNode(no)==true) {
//                return true;
//            } else {
//                return this.right.delNode(no);
//            }
//        } else if (this.right != null) {
//            return this.left.delNode(no);
//        }

        // 递归地在左子树中查找并尝试删除节点
        if (this.left != null && this.left.delNode(no)) {
            return true; // 左子树中删除了节点，递归成功
        }

        // 如果左子树中没有删除节点，继续在右子树中查找并尝试删除节点
        if (this.right != null && this.right.delNode(no)) {
            return true; // 右子树中删除了节点，递归成功
        }
        return false;
    }

}